The present invention relates generally to image data representative of a document to be duplicated and, more particularly, to a method and apparatus for compressing and decompressing image data to reduce the storage capacity or bandwidth required for storage or transmission of the data, respectively.
Data compaction is well known in electrical systems to reduce storage space for data storage or channel bandwidth for data transmission. Data compaction techniques have been applied to image data produced by duplication or facimile systems. In such systems, a document is scanned to generate raw image data with individual data bits corresponding to small elements of the document. The small elements are referred to as picture elements or pels and the image data defines whether each pel is a white, no-print element or a black, print element. The need for compaction of such raw data is appreciated by observing that one square inch of a document may comprise a 400.times.400 matrix of pels for a high quality ink jet duplicating system, i.e., 160,000 pels per square inch.
One known data compaction technique is run-length encoding wherein the number of repetitive occurrences of data bits of a given data state is transmitted rather than the bits themselves. According to run-length encoding, a 5 bit word representing the number 32 is transmitted instead of 32 consecutive and identical data bits. Such run-length encoding has been improved in accordance with a technique referred to as Huffman coding. In Huffman coding, the most commonly encountered run lengths in a document type to be duplicated are allocated to the shortest code words such that fewer bits are required to represent a document.
Run-length and Huffman coding result in varying length code words which generally represent individual scan lines of a document to be duplicated. A dual line compaction technique is disclosed in U.S. Pat. No. 3,916,095, issued to Weber et al. on Oct. 28, 1975. In the disclosed dual line compaction technique, data pairs, i.e., adjacent upper and lower elements of two scan lines, are encoded. Data pairs having the same data state (both white or both black) are run-length encoded and transitional data pairs (upper black/lower white or upper white/lower black) are individually encoded. The coding technique of the cited patent is an adaptive word-length code which results in varying length code words.
While these prior art encoding arrangements provide data compaction for storage or transmission of image data, the resultant varying length code words must be decoded from the first encoded word to the last encoded word. Often, it is desirable to decode an encoded data block either from the first-to-the-last encoded data word of from the last-to-the-first encoded data word. The ability to decode in either direction adds versatility and permits a larger variety of applications. For example, a document may be scanned and encoded in one direction and decoded and printed in the opposite direction to facilitate duplication of the document.
Thus, the need exists for an improved compression/decompression method and apparatus for use, for example, in a duplicating system wherein image data representative of a document is compressed, stored, decompressed in either direction and then utilized to duplicate the document.